Networks are typically formed by one or more interconnected pathways. In a network, items may travel along the various pathways. A network may include more than one pathway from a first location to a second location. The process of selecting among the two or more pathways for the item(s) to travel is termed “routing” for the purposes of this application. Routing may be performed for many kinds of networks, including a telephone network, transportation networks, and an electronic data network (such as a local area network, wide area network, intranet, extranet, or Internet).
For the purposes of this application, the present invention is discussed in reference to routing certain types of items—specifically, information items—through certain types of networks—specifically, electronic data networks —, but the discussion is merely exemplary. The present invention is applicable to routing movement of any type of item through any type of network. For example, certain embodiments of the present invention may be configured to address other multi-commodity flow problems such as traffic engineering road networks and commodity flow in the economy.
As indicated above, certain embodiments of the present invention are directed to routing information in electronic data networks. Electronic data networks may be comprised of at least a group of two or more nodes. An example of a node is a physical electronic device (e.g., a router, computer, or switch). A node also may be a virtual manifestation of such a device. For the purposes of this application, the term “node” is interchangeable with the term “router”.
Typically, information is transferred between nodes in a formatted unit of data, such as a packet, byte, character, datagram, or bit. Certain embodiments of the present invention will be discussed with reference to transfer of information packets, but this discussion is non-limiting and merely exemplary. Generally, any formatted unit of data may be transferred among nodes according to the present invention, or more generally, any commodity may be transferred along pathways in a network.
An information packet may be routed from a source node to a destination node. More specifically, the information packet may travel from a source node directly to a destination node or may travel from a source node to one or more intermediate nodes and then reach a destination node. For the purposes of this application, the portion of the route between each node and a second node is termed a “link”.
The specific nodes through which the information packet travels—which form the “pathway”—may be selected based on some criteria, such as shortest distance between source node and destination node or most bandwidth availability along the pathway. Certain criteria information—e.g., distance between certain nodes—may be obtained and stored in a storage component. Examples of a storage component include a routing table, a topology map, a main memory, or secondary memory (the latter two of which are described in more detail below).
In certain embodiments, each node has its own storage component, which contains information regarding that node's links to other nodes. For example, a storage component for a single node may include the information such as the distance between that single node and each other neighboring node. For the purposes of this application, a “neighboring node” is a node to which a source node can directly transfer information without need for an intermediate node.
Various procedures for routing information packets through the pathways of an electronic data network existed before the present invention. Certain types of earlier known routing procedures are called “link-state routing procedures”. Such procedures are configured to select pathways for the information packets based on the state of the links between nodes. For purposes of this application, the term “link state” refers to a numerical description of the state of the link. It could be a number 1 to indicate a functioning link vs. a number 0 to indicate an inactive link. In another embodiment, the link state could be a valuation of the amount of traffic on the link.
Typically, the shortest distance between a source node and each other node in the network is calculated. The distance may be considered a “price” for the purposes of the calculation. A higher distance has a higher price, and a shorter distance has a lower price. The procedure may seek to minimize the overall price of the set of links that form the pathway. Then, when an information packet travels through the selected pathway, it does so by traveling the shortest distance.
However, such procedures have certain disadvantages in that the pathway with the shortest distance may not be the most efficient pathway. For example, the most efficient pathway may get overburdened and become unable to support the quantity of information packets routed through that pathway. Accordingly, more advanced systems and methods added additional criteria to calculate the “price” of the respective links and overall pathway. For example, such criteria may include available bandwidth between nodes, expected delay in communicating between nodes, pathway reliability, or pathway availability.
In certain known procedures, the route for the information packet is re-analyzed at each node. For example, at a source node, an evaluation is done to assess the “lowest price” second node in light of the ultimate destination node. A second assessment is done at the second node to determine the “lowest price” subsequent node in order to reach the destination node. The analysis is done at every subsequent node until the information packet reaches the destination node. This type of process is called “hop-by-hop” routing because a separate analysis is done relative to each node to determine each subsequent “hop” over a link.
Each network may include more than one packet travelling through the system. In the analysis step done at each node (in systems using the hop-by-hop approach), the selection of which packets or how many packets follow which pathway through which nodes is termed a “split ratio”.
Generally, the “hop-by-hop” routing procedures are limited in that they do not always achieve the optimal route over the entire pathway. For example, in the network illustrated in FIG. 1, if node A is the source node and node D is the destination node, the analysis at node A includes an assessment whether node B or node C has a lower price. The price of the link between node A and node B is rated 4, while the price of the link between node A and node C is rated 10. Accordingly, the analysis will identify node B as the lowest price subsequent node. Then, the analysis at node B will identify node D as the best subsequent node. The overall price will be 18 (calculated by adding link price A-B, 4, and the price of link B to D, 14). However, if the analysis at node A could have all the information about the network analyzed appropriately, it would have calculated that the route from node A-C-D actually has a lower price of 16—calculated by adding A-C Link price of 10 plus C-D Link price of 6—relative to the A-B-D price of 18. The route A-C-D would have optimized the objective of using the lowest price route over the entire network.
In general, “optimized” or “optimal” routing procedures may include a method configured to achieve the most efficient mathematically/physically possible result for any identified objective (e.g. minimize total delay, maximize use of network resources, minimize distance traveled) or combination of objectives determined by a network operator. Alternatively, the objectives may be prioritized by the system either in real-time as the system is processing the routes or by a list of priorities identified before the route processing begins. The problem of optimizing network traffic is termed “traffic engineering” or “TE” for the purposes of this application.
Overall, known routing procedures configured to achieve optimal or near-optimal traffic engineering over a network are associated with many disadvantages. In general, such procedures are typically difficult to implement or manage and may not take into account any change in the conditions of a link in the network. (The ability to recognize and respond to changes in the state of the link or state of the network is called being “adaptive”. More specifically, an “adaptive” routing method is configured to recognize and respond to changes in the state of the network such as the traffic demand of the commodities or packets—as recognized from the input to the method—automatically.) Certain known routing procedures and their respective disadvantages are discussed below.
An alternative to “hop-by-hop” routing is termed “source routing”, in which the entire route from the source node to the destination node is calculated by the source node. Source routing can be difficult to implement, because the source node has to encode, in the information packet, the entire pathway that it must take through the network. This could potentially be more information than the payload of the packet.
Examples of source routing include the flow deviation technique, the gradient projection approach, and proximal decomposition methods. However, these optimization procedures require the network to establish end-to-end virtual circuits or to encode the entire pathway each packet should take at the origin of that packet. As the traffic patterns change, the established circuits become less useful and performance levels decrease.
Instead of using source routing, efforts have been made to improve the optimality of traffic engineering in known hop-by-hop link-state procedures. For example, techniques have been shown to improve the performance of certain hop-by-hop link-state procedures—e.g., Open Shortest Path First (OSPF)—significantly by finding better weight settings for the procedure. However, the results are still far from optimal traffic engineering. Typically, these efforts also assume that a good estimate of the traffic demand in the form of a traffic matrix is available. For the purposes of this application, a “traffic matrix” is a matrix representation of the current traffic demand between the nodes in a network. While work has been done on traffic matrix estimation, even the best results have errors in the elements of the estimated traffic matrix on the order of 20%—difficulties which can lead to potentially bad traffic engineering.
Oblivious routing has been proposed to circumvent the need for estimating the traffic matrix for improved traffic engineering. Such procedures seek to perform well regardless of the traffic demand by comparing the ‘oblivious performance ratio’ of the routing, i.e., the worst case performance of the routing for a given network over all possible demands. Examples of such procedures are a linear programming method to determine the best oblivious routing solution for the special case of minimizing maximum channel utilization and another procedure configured to maximize throughput for the special case of two phase routing. Some clear limitations of these procedures are that the oblivious routing solutions do not adapt well to changes in the network topology and that, by not taking advantage of actual traffic information, the routing still incurs possibly significant performance losses.
Other hop-by-hop routing procedures are based on distance-vector methods. Distance vector methods call for each router to send all or some portion of its routing table to other nodes, but only to its neighboring nodes.
As long as a node has access to the “average price” (e.g., “average distance”) to each destination at each of its neighbors, such as the averages calculated in Equation 1 below, it has enough information to make optimal forwarding decisions. From an optimization standpoint, the main ideas follow directly from the decomposition of the dual of the traffic engineering optimization problem. Such decompositions, which have been very successful for problems of this type, can be used to yield updating rules for both primal and dual variables (split ratios and node prices) that can be shown to converge to optimal solutions. Similar node-based ideas have also been applied to cross-layer optimization of networks.
However, such distance-vector procedures are often difficult to scale up in large networks and lack robustness. More specifically, in one example of the lack of robustness in distance-vector systems, one router started advertising to its neighboring nodes that it has essentially zero distance to all destinations. The neighboring nodes started shifting traffic to this router followed by the neighboring nodes' respective neighboring nodes. Eventually the router went down under the traffic load but many routers in the Internet were still pointing or trying to point towards this router.
Also, distance-vector procedures can converge slowly as packets need to be passed in a step-by-step manner from one end of the network to another for route computations to take place.
Clearly, there are challenges associated with implementing procedures configured to provide optimized traffic engineering in a network. While procedures have been developed to implement optimized procedures of certain portions of a network, the challenges associated with scaling such procedures to appropriate size for certain networks has limited the usefulness of such procedures.
Accordingly, hop-by-hop link-state routing procedures that are not optimized are commonly used in many networks, despite not resulting in optimal use of network resources. Examples of such non-optimized procedures include the Open Shortest Path First (OSPF) procedure and the Intermediate System—Intermediate System (IS-IS) procedure. Such procedures are relatively easy to implement, manage, and scale up, and, accordingly, have been widely applied, but lack optimality.
Clearly, there is a demand for a hop-by-hop, link-state, traffic-optimal routing system and methods for routing items through a network. The present invention satisfies this demand.